#include<stdio.h>

//直接插入排序
void InsertSort(int* parr, int n)
{
  int i = 0;
  for(i = 0; i < n - 1; i++)
  {
    int end = i;
    int key = parr[end + 1];
    while(end >= 0)
    {
      if(key < parr[end])
      {
        parr[end + 1] = parr[end];
        end--;
      }
      else
      {
        break;
      }
    }
    parr[end + 1] = key;
  }
}

//希尔排序
void ShellSort(int* parr, int n)
{
  //分组控制
  int grp = n;
  while(grp > 1)
  {
    //调整组距
    grp /= 2;

    int i = 0;
    for(i = 0; i < n - grp; i++)
    {
      int end = i;
      int key = parr[end + grp];
      while(end >= 0)
      {
        if(key < parr[end])
        {
          parr[end + grp] = parr[end];
          end -= grp;
        }
        else
        {
          break;
        }
      }
      parr[end + grp] = key;
    }
  } 
}

void PrintArr(int* parr, int sz)
{
  int i = 0;
  for(i = 0; i < sz; i++)
  {
    printf("%d ", parr[i]);
  }
  printf("\n");
}

void TestInsertSort()
{
  int arr[] = { 4, 0, 3, 2, 7, 5, 6, 9, 8, 1 };
  int sz = sizeof(arr)/sizeof(arr[0]);
  InsertSort(arr, sz);
  PrintArr(arr, sz);
}

void TestShellSort()
{
  int arr[] = { 4, 0, 3, 2, 7, 5, 6, 9, 8, 1 };
  int sz = sizeof(arr)/sizeof(arr[0]);
  ShellSort(arr, sz);
  PrintArr(arr, sz);
}

#define N 2
#define M N + 1
#define NUM (M + 1) * M / 2

int minimumMoves(char * s) 
{
   int covered = -1, res = 0;
   for (int i = 0; s[i] != '\0'; i++) 
   {
       if (s[i] == 'X' && i > covered) 
       {
           res += 1;
           covered = i + 2;
       }
   }
   return res;
}

void test()
{
  
}

int main()
{
  //printf("%d\n", NUM);
  //TestInsertSort();
  //TestShellSort();
  test();
  return 0;
}
